МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное

учреждение высшего образования

«ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет управления

КУРС ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

Функциональное программирование и интеллектуальные системы

Кафедра математическое моделирование, эконометрика и статистика факультета управления

Образовательная программа

38.03.05 Бизнес-информатика

Разработчик: кафедра «Математическое моделирование, эконометрика и статистика», Рабаданова Р.М. к.э.н., доцент

Махачкала, 2020 год

Тема 1. Введение в функциональное программирование.

1. Введение.

2. Функциональный стиль программирования

Функциональное программирование – это ветвь программирования, при котором программирование ведется с помощью определения функций. Функциональном программировании нет ни процедур, ни циклов, нет даже переменных. Почти одни только функции. Функциональное программирование обладает рядом очень существенных преимуществ, которые не только позволяют ему существовать наряду с традиционным программированием, но и иметь своих поклонников, свою нишу задач и хорошие перспективы на будущее.

Традиционное программирование родилось в 40-х годах 20 века, когда велась разработка первых электронно-вычислительных машин (ЭВМ). Его основой послужила концепция фон Неймана о хранимой программе автоматических вычислений по заданному алгоритму. Существенными чертами такой программы служили, во-первых, строгая последовательность в выполнении ее элементарных шагов и, во-вторых, возможность хранения и изменения программы наряду с данными для вычислений в общей с ними памяти. Таким образом, программа сама становилась объектом обработки вместе с арифметическими значениями, над которыми, собственно, и должны были производиться все действия.

Когда появились первые компьютеры, то их устройство следовало принципам, сформулированным фон Нейманом (архитектура фон Неймана). Исполнение программ в первых электронно-вычислительных машинах сводилось к выполнению арифметическим устройством (позже оно стало называться процессором) элементарных шагов, называемых командами, которые строго последовательно производили определенные действия над арифметическими значениями или другими командами, хранящимися в оперативной памяти компьютера. Изменять команды нужно было для того, чтобы организовать циклическое повторение участков программы и своевременное завершение таких повторений.

В конце 50-х годов 20 века появились первые языки программирования высокого уровня, в них уже произошел существенный отход от принципов фон Неймана. Во-первых, программа раз и навсегда была отделена от данных. Во-вторых, во время исполнения программы ее текст оставался неизменным, а организация циклического повторения команд в ходе исполнения программы была возложена на систему программирования, которая уже и должна была перевести (транслировать) текст программы в систему команд компьютера так, чтобы ее исполнение происходило в соответствии с написанным текстом. Единственный принцип, остававшийся неизменным, был принцип последовательного исполнения, в соответствии с которым исполнение программы можно было разложить на строго последовательные элементарные шаги алгоритма. Поэтому до сих пор программирование в традиционном стиле часто называют «фон-Неймановским».

Со временем принцип последовательного исполнения стал серьезным препятствием для развития компьютерной техники. Самым узким местом вычислительных систем уже долгое время остается тот самый процессор, который последовательно исполняет элементарные команды. Конечно, скорость работы современных процессоров не сравнить со скоростью работы арифметических устройств первых ЭВМ, однако, производительность компьютеров сейчас, как и раньше, ограничена, в основном, именно этим центральным устройством. Именно скорость работы центрального процессора имеет решающее значение при определении общей производительности компьютера.

Скорость работы процессора стала зависеть уже не столько от его архитектуры и технологических элементов, сколько просто от его размеров, потому что на скорость работы решающее влияние стала оказывать скорость прохождения сигналов по цепям процессора, которая, как известно, не может превысить скорости света. Чем меньше процессор, тем быстрее смогут внутри него проходить сигналы, и тем больше оказывается конечная производительность процессора. Размеры процессора уменьшились многократно, однако, все труднее стало отводить от такого миниатюрного устройства вырабатываемое при работе его элементов тепло. Перед производителями вычислительной аппаратуры встал очень серьезный вопрос: дальнейшее повышение производительности стало почти невозможным без изменения основополагающего принципа всего современного программирования – последовательного исполнения команд.

Конечно, можно так спроектировать вычислительную систему, чтобы в ней могли одновременно работать несколько процессоров, но, к сожалению, это почти не дает увеличения производительности, потому что все программы, написанные на традиционных языках программирования, предполагают последовательное выполнение элементарных шагов алгоритма почти так же, как это было во времена фон Неймана. Время от времени предпринимаются попытки ввести в современные языки программирования конструкции для параллельного выполнения фрагментов кода, однако языки "сопротивляются". Оказывается, думать об организации параллельного выполнения фрагментов программы – этодовольно сложная задача, которая успешно решается человеком только для весьма ограниченных случаев.

Проблему можно решать различными способами. Во-первых, можно попробовать написать специальную программу, которая могла бы проанализировать имеющийся программный текст и автоматически выделить в ней фрагменты, которые можно выполнять параллельно. К сожалению, такой анализ произвольного программного кода очень труден. Последовательность выполнения шагов алгоритма очень трудно предсказать по внешнему виду программы, даже если программа «хорошо структурирована». Второй способ перейти к параллельным вычислениям – это создать такой язык программирования, в котором сам алгоритм имел бы не последовательную структуру, а допускал бы независимое исполнение отдельных частей алгоритма. Но против этого восстает весь накопленный программистами опыт написания программ.

Тем не менее, оказалось, что опыт написания программ, не имеющих строго последовательной структуры, на самом деле есть. Почти одновременно с первым "традиционным" языком программирования – Фортраном появился еще один совершенно непохожий на него язык программирования – Лисп, для которого последовательность выполнения отдельных частей написанной программы была несущественной. Ветвь программирования, начатая созданием Лиспа, понемногу развивалась с начала 60-х годов 20 века и привела к появлению целой плеяды очень своеобразных языков программирования, которые удовлетворяли всем требованиям, необходимым для исполнения программ несколькими параллельными процессорами. Во-первых, алгоритмы, записанные с помощью этих языков, допускают сравнительно простой анализ и формальные преобразования программ, а во-вторых, отдельные части программ могут исполняться независимо друг от друга. Языки, обладающие такими замечательными свойствами – это и есть языки функционального программирования.

Помимо своей хорошей приспособленности к параллельным вычислениям языки функционального программирования обладают еще рядом приятных особенностей. Программы на этих языках записываются коротко, часто много короче, чем в любом другом традиционном (императивном) языке. Описание алгоритмов в функциональном стиле сосредоточено не на том, как достичь нужного результата (в какой последовательности выполнять шаги алгоритма), а больше на том, что должен представлять собой этот результат.

Пожалуй, единственный серьезный недостаток функционального стиля программирования состоит в том, что этот стиль не универсальный. Многие действительно последовательные процессы, такие как поведение программных моделей в реальном времени, игровые и другие программы, организующие взаимодействие компьютера с человеком, не выразимы в функциональном стиле. Тем не менее, функциональное программирование заслуживает изучения хотя бы еще и потому, что позволяет несколько по-иному взглянуть вообще на процесс программирования, а некоторые приемы программирования, которые, вообще говоря, предназначены для написания программ в чисто функциональном стиле, могут с успехом использоваться и в традиционном программировании.

2. Функциональный стиль программирования

Часто процесс исполнения программы можно представить схемой, показанной на рисунке 1.1.

Рис. 1.1. Схема простой программы

Конечно, не любую программу можно представить в виде такой схемы, а только такую, которая, получив некоторые входные данные в начале своей работы, затем обрабатывает их, не общаясь с внешней средой, и в конце работы выдает некоторый результат. Часто такую схему работы программы называют «черным ящиком», подразумевая, что в этой схеме нас не интересует, как и в какой последовательности происходят те или иные действия в программе, а интересует только то, какой результат получается в зависимости от входных данных. Можно сказать, что при такой схеме работы результат находится в функциональной зависимости от исходных данных.

Можно привести много примеров простых и сложных программ, имеющих смысл и работающих по этой схеме. Например, программа аналитических преобразований выражений – входными и выходными данными здесь будут выражения, представленные в разной форме. Еще пример: компилятор с некоторого языка программирования – входными данными программы будет текст, написанный на этом языке программирования, а выходными данными – объектный код программы. Третий пример: программа составления расписания учебных занятий – исходные данные для такой программы – набор «пожеланий» к расписанию, а выходные данные – таблица, представляющая расписание занятий. В то же время многие программы выполняются не по схеме «черного ящика». Например, любая программа, организующая активное взаимодействие (диалог) с пользователем, не является преобразователем набора входных данных в выходные, если только не считать, что входными и выходными данными в этом случае является «среда», включающая в том числе и пользователя.

Всякая программа, написанная в функциональном стиле – это программа, представляющая собой функцию, аргументом которой служат входные данные из некоторого допустимого набора, и выдающую определенный результат. Обычно при этом подразумевается, что функция, определяющая поведение программы, на одних и тех же входных данных всегда выдает один и тот же результат, то есть функция детерминированная. Можно заметить, что любая программа, содержащая запросы к пользователю (взаимодействующая с пользователем) – не детерминированная, поскольку ее поведение может зависеть от «поведения пользователя», то есть конкретных данных, введенных пользователем. Отличительными особенностями функций, определяемых любым языком функционального программирования, являются следующие черты:

Каждая функция в программе выдает один и тот же результат на одном и том же наборе входных данных (аргументов функции), то есть результат работы функции является «повторяемым».

Вычисление функции не может повлиять на результат работы других функций, то есть функции являются «чистыми».

Если программа состоит только из чистых функций, то порядок вычисления аргументов этих функций будет несущественным. Вообще, любые выражения, записанные в такой программе по отдельности, независимо друг от друга (вычисление значений отдельных элементов списка, полей кортежа и т.п.) могут вычисляться в любой последовательности или даже параллельно. При наличии нескольких независимых процессоров, работающих в общей памяти, вычисления, происходящие по программе, составленной только из вызовов чистых функций, легко распараллелить. Уже это свойство функционального стиля программирования привлекает к нему значительный интерес.

Можно ли писать программы в функциональном стиле на традиционном языке программирования? Конечно, да. Если программа представляет из себя набор чистых детерминированных функций, то она будет "функциональной" независимо от того, написана ли она на специальном языке функционального программирования Haskell или на традиционной Java. Рассмотрим, например, задачу вычисления числа вещественных корней заданного квадратного уравнения. Функция, решающая эту задачу должна, получив в качестве исходных данных коэффициенты квадратного уравнения, вычислить его дискриминант, а затем сформировать нужный результат в зависимости от знака вычисленного дискриминанта. На языке Java функция может выглядеть следующим образом (листинг 1.1).

Листинг 1.1. Функция вычисления числа корней квадратного уравнения

int roots(double a, double b, double c) {

double discr = b * b - 4 * a * c;

if (discr < 0) return 0; else

if (discr == 0) return 1; else

return 2; }

Эта функция, конечно же, детерминированная и «чистая», однако все же с точки зрения функционального стиля она имеет одну «неправильность». Дело в том, что в функции определяется и используется локальная переменная discr, которая используется для запоминания значения дискриминанта квадратного уравнения. В данном случае это никак не влияет на «чистоту» написанной функции, но если бы внутри функции были бы определены другие функции, то результат их работы мог бы быть различным в зависимости от того, когда они вызываются – до присваивания переменной discr нового значения или после него. Поэтому чисто функциональный стиль программирования предполагает полное отсутствие присваиваний в программах.

Кроме того, в чисто функциональных программах нет понятия последовательного вычисления. Каждая функция должна представлять собой суперпозицию обращений к другим функциям. В нашем же примере порядок вычислений задается строго, в нем предписывается, что сначала требуется вычислить значение дискриминанта и присвоить вычисленное значение переменной discr, потом проверить, верно ли, что полученная переменная имеет значение, меньшее нуля, и т.д.

Впрочем, в нашем случае исправить программу, приведя ее в соответствие с принципами функционального стиля программирования, довольно просто. Для этого определим две вспомогательные функции для вычисления дискриминанта квадратного уравнения и для вычисления знака вещественного числа (аналогичную стандартной Math.signum, но выдающую целый результат). В результате получится следующая программа (листинг 1.2).

Листинг 1.2. Функция вычисления корней квадратного уравнения

double discr (double a, double b, double c) {

return b * b - 4 * a * c; } int sign (double x) {

return x < 0 ? -1 : x == 0 ? 0 : 1; } int roots(double a, double b, double c) {

return sign(discr(a, b, c)) + 1;

}

Эта программа уже действительно чисто функциональная. Обратите внимание также и на то, что вместо условных операторов мы в этой программе используем условные выражения, которые соединяют условиями не отдельные части последовательно выполняющейся программы, а отдельные подвыражения. Это тоже является характерной особенностью функционального стиля программирования.

Однако, убрав возможность присваивания значений переменным, мы тем самым сделали бессмысленным использование и одного из самых мощных средств традиционного программирования – циклов. Действительно, циклы имеют смысл только в том случае, если при каждом исполнении тела цикла внешняя среда (совокупность значений доступных в данный момент переменных) хотя бы немного, но меняется. В противном случае цикл либо не исполняется ни разу, либо будет продолжать выполняться бесконечно. Как же в отсутствие циклов написать хотя бы такую простую функцию, как вычисление факториала заданного натурального числа?

Альтернативой циклам являются рекурсивные функции, так что задачу написания функции для вычисления факториала числа все же можно решить на Java в чисто функциональном стиле (листинг 1.3):

Листинг 1.3. Функция вычисления факториала натурального числа

int factorial (int n) {

return n == 0 ? 1 : n * factorial(n-1); }

Тогда, может быть, для того, чтобы писать в функциональном стиле, нужно просто взять привычный язык, ну, скажем, ту же Java, и «выкинуть» из него переменные, присваивания и циклы, вообще любые «последовательные» операторы? Конечно, в результате действительно получится язык, на котором программы будут всегда написаны «в функциональном стиле», но получившийся язык будет слишком бедным для того, чтобы на нем можно было писать действительно полезные программы. В «настоящих» языках функционального программирования с функциями можно работать значительно более гибко, чем позволяется в традиционных языках программирования. Рассмотрим следующую простую задачу.

Пусть требуется определить функцию, с помощью которой можно создавать суперпозицию двух вещественных функций одного вещественного аргумента. Другими словами, требуется описать инструмент, с помощью которого из двух произвольных функций f(x) и g(x) можно было бы получить новую функцию fg(x), результат работы которой определялся бы уравнением fg(x) = f(g(x)). Конечно, решение этой задачи было бы очень полезным в ситуации, когда практически единственным инструментом программирования является определение и вызов различных функций. На первый взгляд кажется, что задачу легко запрограммировать на «чуть-чуть расширенной» Java, в которой достаточно лишь разрешить описывать тип функциональных значений и возвращать функции в качестве результата работы других функций (возможно, эта возможность появится в JDK 7, однако, на момент написания книги эта информация еще не подтверждена окончательно). Еще одна «мелочь», которую мы будем использовать в расширенной Java – это возможность определения нового идентификатора типа с помощью typedef. Поставленная задача может быть решена на расширенной Java следующим образом (листинг 1.4).

Листинг 1.4. Реализация суперпозиции на Java typedef Func = #double(double);

Func comp(Func f, Func g) {

final Func result = #double(double x) { return f(g(x)); };

return result; }

К сожалению, не очень понятно, сможет ли такая программа работать даже в расширенном варианте языка Java. Причина этого заключается в том, что функция result, определенная внутри функции comp, использует глобальные для нее значения функциональных аргументов f и g. После выхода из функции comp связь этих аргументов с фактическими значениями может быть потеряна. Попробуем, скажем, выполнить вызов следующей функции, полученной с помощью comp

comp(sin, cos)(3.14)

При вызове comp(sin, cos) будет образовано новое функциональное значение, представленное функцией result в определении функции comp. Однако функция result ссылается на аргументы f и g, а их связь с функциями sin и cos может быть потеряна после выхода из функции comp. В этом случае вызов новой функции с аргументом 3.14 не сможет проработать правильно. Для того, чтобы эта программа работала правильно, необходимо кардинально пересмотреть подход к образованию функциональных значений.

Описанное поведение заложено в структуре традиционных языков, рассчитанных на последовательное исполнение шагов алгоритма, очень глубоко, и для того, чтобы можно было писать программы для решения задач вроде только что описанной, требуется определять языки с совершенно другими свойствами. Этой цели и служат специализированные языки функционального программирования. В частности, в этих языках функции являются значениями «первого класса», то есть с ними можно проделывать все то же, что и с другими «обычными» значениями: над ними можно выполнять операции и применять к ним другие функции как к

аргументам; можно написать функцию, результатом работы которой будет также функция; функции могут быть элементами сложных структур данных и т.п.

Кстати, программу, содержащую функцию, похожую на comp, все же можно написать и на чистом языке Java. Для этого надо использовать вместо представлений в виде функции представления в виде реализаций некоторого специального интерфейса.

Тема 2. Основы функционального программирования на яыке F#

Наверняка в последнее время вы хоть что-то слышали о F# — новейшем пополнении в семействе языков для Microsoft Visual Studio. Для изучения F# есть много веских причин:четкий синтаксис, мощные средства работы с множеством потоков и способность к взаимодействию с другими языками, совместимыми с Microsoft .NET Framework. Однако F# включает несколько новых важных концепций, в которые нужно вникнуть, прежде чем пользоваться ими.

Краткий экскурс — неплохой способ приступить к освоению другого объектно-ориентированного языка или даже динамического языка вроде Ruby или Python. Такое возможно потому, что вам уже известна большая часть словарного запаса подобных языков и вы просто изучаете новый синтаксис. Но F# стоит здесь особняком. F# — это язык функционального программирования, и его словарь отличается куда больше, чем вы могли бы ожидать. Более того, функциональные языки традиционно применялись в академических кругах, поэтому определения совершенно новых для вас терминов могут оказаться сложными в понимании.

К счастью, F# проектировали вовсе не как академический язык. Его синтаксис позволяет с помощью методик функционального программирования решать задачи новыми и более эффективными способами, в то же время поддерживая объектно-ориентированные и императивные стили, к которым вы привыкли как .NET-разработчик. В отличие от других .NET-языков структура F# на основе множества парадигм означает, что вы свободны в выборе наиболее подходящего для конкретной задачи стиля программирования. Функциональное программирование в F# заключается в написании четкого и эффективного кода для решения проблем реального программного обеспечения. Оно завязано на такие методики, как применение функций более высокого порядка (higherorderfunctions) и композиция функций (functioncomposition) для создания эффективных и простых в понимании поведений. И оно же состоит в том, чтобы ваш код было легче воспринимать, тестировать и распараллеливать, удаляя скрытые сложности.

Но, чтобы воспользоваться преимуществами всех этих фантастических средств F#, нужно разобраться в основах

Основы функционального программирования

Большинству .NET-разработчиков легче понять функциональное программирование, отталкиваясь от обратного — от того, чем оно не является. Императивное программирование считается стилем, прямо противоположным функциональному. Это также стиль, с которым вы, вероятно, знакомы лучше всего, поскольку большинство мейнстримовых языков программирования являются императивными.

Функциональное и императивное программирование отличаются на фундаментальном уровне, и это можно увидеть даже в таком простейшем коде:

intnumber = 0;

number++;

Очевидно, что здесь значение переменной увеличивается на единицу. Ничего особенного, но взгляните на другой способ решения той же задачи:

constint number = 0;

constint result = number + 1;

Значение number по-прежнему увеличивается на единицу, но оно не модифицируется по месту. Результат сохраняется как другая константа, потому что компилятор не разрешает изменять значение константы. Константы неизменяемы, потому что их значения нельзя модифицировать после определения. И напротив, переменная number в первом примере была изменяемой, так как вы могли модифицировать ее значение. Эти два подхода иллюстрируют одно из фундаментальных различий между императивным и функциональным программированием. В императивном программировании делается упор на использование изменяемых переменных, тогда как в функциональном — на применение неизменяемых значений.

Большинство .NET-разработчиков сказало бы, что number и result в предыдущих примерах являются переменными, но как «функциональный» программист вы должны аккуратнее подбирать слова. В конце концов, одна лишь идея постоянной переменной может просто запутать в лучшем случае. Вместо этого в функциональном программировании говорят, что number и result являются значениями. Термин «переменная» резервируется за объектами, которые можно изменять. Заметьте, что эти термины — не эксклюзив функционального программирования, но они гораздо важнее при программировании в функциональном стиле.

Разница может показаться незначительной, но это фундамент множества концепций, которые и делают функциональное программирование таким эффективным. Изменяемые переменные являются корневой причиной многих неприятнейших ошибок. Как вы увидите, они ведут к неявным зависимостям между различными частями вашего кода, что создает массу проблем, особенно в сочетании с параллельным выполнением. В противоположность этому неизменяемые переменные убирают значительную часть проблем. Они делают возможным применение методик функционального программирования, при котором, например, функции используются как значения, и композиционного программирования, о котором я также расскажу подробнее чуть позже.

Рассмотрим такой пример:

stringstringValue = "world!";

string result = stringValue.Insert(0, "hello ");

Функция Insert формирует строку «helloworld!», но вы знаете, что Insert не модифицирует исходную строку. А все потому, что в .NET строки неизменяемы. Проектировщики .NET Framework использовали здесь функциональный подход, так как он упрощает написание более качественного кода, работающего со строками. Поскольку строки — один из самых широко применяемых типов данных в .NET Framework (наряду с другими базовыми типами вроде целых, DateTimes и прочими), все шансы за то, что на самом деле вы шире используете функциональное программирование, чем вам это кажется.

3. F# и Visual Studio 2010

F# поставляется с Visual Studio 2010, и самую последнюю его версию можно найти по ссылке msdn.microsoft.com/vstudio.

F# добавляет в Visual Studio новое окно — F# Interactive, которое позволяет интерактивно выполнять код на F#. Вы можете считать его более мощной версией окна Immediate, доступной даже в том случае, если вы не переключались в режим отладки. Если вы знаете Ruby или Python, то заметите, что F# Interactive выполняет цикл «чтение-оценка-вывод» (Read-Evaluate-PrintLoop, REPL), который является полезным средством для освоения F# и возможностью быстро поэкспериментировать с кодом.

Если вы выделите какой-то код в Visual Studio и нажмете Alt+Enter, то отправите его в F# Interactive. Возьмем простойпример на F#:

let number = 0

let result = number + 1

Запустив этот код в F# Interactive, вы получите следующее:

val number : int = 0

val result : int = 1

Вероятно, вы уже догадались по ключевому слову val, что number и result являются неизменными значениями. Вы можете увидеть это, использовав оператор присваивания (<-) в F#:

>number<- 15;;

number<- 15;;

^^^^^^^^^^^^

stdin(3,1): error FS0027: This value is not mutable

Поскольку вы теперь знаете, что функциональное программирование основано на неизменяемости, эта ошибка должна быть вам понятной. Ключевое слово let используется для создания неизменяемых привязок между именами и значениями. В терминологии C# то же самое можно было сказать так:по умолчанию в F# все является константами. Вы можете сделать переменную изменяемой, но только явным образом. По умолчанию поведение прямо противоположно тому, к чему вы привыкли в императивных языках:

letmutablemyVariable = 0

myVariable<- 15

Логическое распознавание типов и чувствительность к пробелам и отступам

F# позволяет объявлять переменные и значения без указания их типов, поэтому можно подумать, будто F# является динамическим языком, но это не так. Важно понимать, что F# такой же статический язык, как C# или C++. Однако F# имеет мощную систему логического распознавания типов (type inference), которая позволяет во многих местах не указывать типы объектов. Это упрощает синтаксис и делает его лаконичнее, в то же время сохраняя безопасность типов, присущую статическим языкам.

Хотя такие системы логического распознавания типов в действительности отсутствуют в императивных языках, само по себе распознавание типов не связано напрямую с функциональным программированием. Однако распознавание типов — критическая важная концепция, которую нужно понять, если вы хотите освоить F#. К счастью, если вы знаете C#, то наверняка уже знакомы с базовой концепцией логического распознавания типов из-за ключевого слова var:

// Here, the type is explictily given

Dictionary<string, string> dictionary =

new Dictionary<string, string>();

// but here, the type is inferred

var dictionary = new Dictionary<string, string>();

Обе строки кода на C# создают новые переменные, которые статически типизируются как Dictionary<string, string>, но во втором случае ключевое слово var сообщает компилятору логически определять тип переменной за вас. F# выводит эту концепцию на новый уровень. Например, вот функция add в F#:

let add x y =

x + y

let four = add 2 2

В приведенном выше коде нет ни одного указания типа, но F# Interactive раскрывает статическую типизацию:

val add : int ->int ->int

val four : int = 4

Смысл стрелок я подробнее объясню потом, а пока вы можете интерпретировать это так:функцияadd принимает два int-аргумента, а four является значением типа int. Компилятор F# смог логически распознать все типы, исходя из определений add и four. Компилятор использует при этом правила, которые выходят за рамки данной статьи, но, если вас это интересует, вы можете узнать больше в F# DeveloperCenter.

Логическое распознавание типов — один из способов, с помощью которых F# удаляет лишний «шум» из вашего кода, но обратите внимание еще и на отсутствие фигурных скобок и ключевых слов, обозначающих тело функции add или ее возвращаемое значение. А все дело в том, что F# по умолчанию является языком, чувствительным к пробелам и отступам. В F# вы указываете тело функции простыми отступами, а возвращаемое значение — тем, что оно находится в последней строке функции. По аналогии с распознаванием типов чувствительность к пробелам и отступам не имеет прямого отношения к функциональному программированию, но вы должны быть знакомы с этой концепцией, чтобы пользоваться F#.

Побочные эффекты

Теперь вы знаете, что функциональное программирование отличается от императивного тем, что опирается на неизменяемые значения, а не на модифицируемые переменные, но сам по себе этот факт не слишком полезен. Следующее, в чем нам предстоит разобраться, — побочные эффекты (sideeffects).

В императивном программировании вывод функции зависит от ее входного аргумента и текущего состояния программы. В функциональном — функция зависит только от своих входных аргументов. Иначе говоря, когда вы вызываете функцию более одного раза с одним и тем же входным значением, вы всегда получаете одно и то же выходное значение. Причина, по которой этого нет в императивном программировании, связана с побочными эффектами, как показано на рис. 1.

Рис. 1 Побочные эффекты изменяемые переменных

publicMemoryStreamGetStream() {

var stream = new MemoryStream();

var writer = new StreamWriter(stream);

writer.WriteLine("line one");

writer.WriteLine("line two");

writer.WriteLine("line three");

writer.Flush();

stream.Position = 0;

return stream;

}

[TestMethod]

public void CausingASideEffect() {

using (var reader = new StreamReader(GetStream())) {

var line1 = reader.ReadLine();

var line2 = reader.ReadLine();

Assert.AreNotEqual(line1, line2);

}

При первом вызове ReadLine поток данных считывается, пока не встретится символ перевода на новую строку. Потом ReadLine возвращает весь текст вплоть до новой строки. Между этими операциями изменяемая переменная, представляющая позицию в потоке данных, обновляется. Это и есть побочный эффект. При втором вызове ReadLine значение этой переменной (Position) уже изменилось, поэтому ReadLine возвращает другое значение.

А теперь рассмотрим одно из самых важных следствий использования побочных эффектов. Во-первых, взгляните на простой класс PiggBank и некоторые методы для работы с ним ( рис. 2).

Рис. 2 ИзменяемыеPiggyBank

public class PiggyBank{

publicPiggyBank(int coins){

Coins = coins;

}

publicint Coins { get; set; }

}

private void DepositCoins(PiggyBankpiggyBank){

piggyBank.Coins += 10;

}

private void BuyCandy(PiggyBankpiggyBank){

if (piggyBank.Coins< 7)

throw new ArgumentException(

"Not enough money for candy!", "piggyBank");

piggyBank.Coins -= 7;

}

Если у вас есть свинья-копилка с пятью монетками внутри, вы можете вызвать DepositCoins до BuyCandy, но обратное приведет к генерации исключения:

// this works fine

varpiggyBank = new PiggyBank(5);

DepositCoins(piggyBank);

BuyCandy(piggyBank);

// but this raises an ArgumentException

varpiggyBank = new PiggyBank(5);

BuyCandy(piggyBank);

DepositCoins(piggyBank);

ФункцииBuyCandyиDepositCoinsобновляютсостояниесвиньи-копилкичерезпобочныйэффект. Соответственно поведение каждой функции зависит от состояния этой копилки. Поскольку число монеток изменяемое, порядок вызова этих функций имеет значение. Другими словами, между двумя этими методами существует неявная зависимость.

Давайте сделаем число монеток только для чтения, чтобы имитировать неизменяемую структуру данных. На рис. 3 показано, что BuyCandy и DepositCoins теперь возвращают новые объекты PiggyBank вместо обновления существующего PiggyBank.

Рис.3 НеизменяемыеPiggyBank

public class PiggyBank{

publicPiggyBank(int coins){

Coins = coins;

}

publicint Coins { get; private set; }

}

privatePiggyBankDepositCoins(PiggyBankpiggyBank){

return new PiggyBank(piggyBank.Coins + 10);

}

privatePiggyBankBuyCandy(PiggyBankpiggyBank){

if (piggyBank.Coins< 7)

throw new ArgumentException(

"Not enough money for candy!", "piggyBank");

return new PiggyBank(piggyBank.Coins - 7);

}

Как и раньше, если вы попытаетесь вызвать BuyCandy до DepositCoins, вы получите исключение:

// still raises an ArgumentException

varpiggyBank = new PiggyBank(5);

BuyCandy(piggyBank);

DepositCoins(piggyBank);

Но даже если вы поменяете порядок вызовов на обратный, вы получите тот же результат:

// now this raises an ArgumentException, too!

varpiggyBank = new PiggyBank(5);

DepositCoins(piggyBank);

BuyCandy(piggyBank);

Здесь BuyCandy и DepositCoins зависят только от своих входных аргументов, так как число монеток неизменно. Вы можете выполнять эти функции в любом порядке, и результат будет одним и тем же. Неявная зависимость между функциями исчезла. Однако, если вы хотите успешного выполнения BuyCandy, то должны сделать результат BuyCandy зависимым от выхода DepositCoins. Вводить такую зависимость нужно явным образом:

varpiggyBank = newPiggyBank(5);

BuyCandy(DepositCoins(piggyBank));

Это тонкое различие с далеко идущими последствиями. Общее изменяемое состояние и неявные зависимости являются источником некоторых из самых трудноуловимых «багов» в императивном коде и причиной, по которой многопоточное программирование столь сложно в императивных языках. Когда приходится заботиться о порядке выполнения функций, вы должны опираться на громоздкие механизмы блокировки, иначе все пойдет наперекосяк. Чисто функциональные программы свободны от побочных эффектов и неявных зависимостей синхронизации, так что порядок выполнения функций не имеет никакого значения. То есть вам не нужно волноваться о механизмах блокировки и прочих, крайне подверженных ошибкам методиках многопоточного программирования.

Простота работы с множеством потоков является основной причиной того, что в последнее время функциональное программирование привлекает повышенное внимание, но у него есть и много других преимуществ. Функции, свободные от побочных эффектов, легче тестировать, поскольку они полагаются только на свои входные аргументы. Они проще в сопровождении, потому что не полагаются неявно на логику из других функций. Функции, свободные от побочных эффектов, также имеют тенденцию к большей компактности и простоте в комбинировании. О последнем я расскажу подробнее чуть позже.

В F# вы оцениваете функции по их значениям результатов, а не по побочным эффектам. В императивных языках функции обычно вызываются для выполнения чего-либо, а в функциональных — для получения некоего результата. Вы можете увидеть это в F#, взглянув на выражение if:

letisEven x =

if x % 2 = 0 then

"yes"

else

"no"

Вы уже знаете, что в F# последняя строка функции это ее возвращаемое значение, но в этом примере в последней строке функции содержится выражение if. Это не трюк компилятора. В F# даже выражения if спроектированы на возврат значений:

let isEven2 x =

let result =

if x % 2 = 0 then

"yes"

else

"no"

result

Значение result имеет тип string и присваивается прямо выражению if. Здесь есть аналогия с тем, как работает условный оператор в C#:

string result = x % 2 == 0 ? "yes" : "no";

Условный оператор возвращает значение, не создавая побочного эффекта. Это более функциональный подход. В противоположность этому выражение if в C# более императивное, так как не возвращает результат. Все, что оно делает, вызывает побочные эффекты.

Композиция функций

Теперь, когда мы увидели некоторые из преимуществ функций, свободных от побочных эффектов, вы готовы задействовать их полный потенциал в F#. Для начала рассмотрим код на C#, который возводит в квадрат числа от 0 до 10:

IList<int> values = 0.Through(10).ToList();

IList<int>squaredValues = new List<int>();

for (inti = 0; i<values.Count; i++) {

squaredValues.Add(Square(values[i]));

}

Не считая вспомогательных методов Through и Square, этот код вполне стандартен для C#. Хорошие программисты на C#, вероятно, поморщились бы от моего использования цикла for вместо foreach — и были бы правы. Современные языки вроде C# предоставляют циклы foreach в качестве абстракции для упрощения перебора перечислений, избавляя от необходимости явных индексаторов. В этом они преуспели, но взгляните на код на рис. 4.

Рис. 4 Использованиецикловforeach

IList<int> values = 0.Through(10).ToList();

// square a list

IList<int>squaredValues = new List<int>();

foreach (int value in values) {

squaredValues.Add(Square(value));

}

// filter out the even values in a list

IList<int> evens = new List<int>();

foreach(int value in values) {

if (IsEven(value)) {

evens.Add(value);

}

// take the square of the even values

IList<int> results = new List<int>();

foreach (int value in values) {

if (IsEven(value)) {

results.Add(Square(value));

}

В этом примере циклы foreach очень похожи, но тело каждого цикла выполняет немного разные операции. Императивные программисты давно привыкли к такому дублированию кода, потому что этот код считается идиоматическим.

Функциональные программисты используют иной подход. Вместо создания абстракций наподобие циклов foreach, помогающих перебирать списки, они применяют функции, свободные от побочных эффектов:

let numbers = {0..10}

letsquaredValues = Seq.map Square numbers

Этот код на F# тоже возводит в квадрат последовательность чисел, но делает это с помощью функции более высокого порядка. Это просто функции, которые принимают в качестве входного аргумента другую функцию. В данном случае функция Seq.map принимает функцию Square в качестве аргумента. Она применяет эту функцию к каждому числу в последовательности и возвращает последовательность чисел, возведенных в квадрат. Именно из функций более высокого порядка многие говорят, что в функциональном программировании функции используются как данные. Это означает лишь то, что функции можно передавать как параметры или присваивать значениям либо переменным точно так же, как типы int или string. В терминологии C# функции более высокого порядка очень сильно напоминают концепцию делегатов и лямбда-выражений.

Применение функций более высокого порядка — одна из методик, которые делают функциональное программирование таким мощным. С их помощью вы можете выделить дублируемый в циклах foreach код и инкапсулировать его в автономные и свободные от побочных эффектов функции. Каждая из этих функций выполняет одну небольшую операцию, которую обрабатывал бы код внутри соответствующего цикла foreach. Поскольку они свободны от побочных эффектов, вы можете комбинировать их для создания более читаемого и простого в сопровождении кода, который делает то же самое, что и циклы foreach:

letsquareOfEvens =

numbers

|>Seq.filterIsEven

|>Seq.mapSquare

Единственная непонятная часть этого кода — оператор |>. Этот оператор используется для большей читаемости кода, разрешая вам переупорядочивать аргументы в функции, чтобы последний аргумент первым попался вам на глаза. Его определение очень простое:

let (|>) x f = f x

Без оператора |> код squareOfEvens выглядел бы так:

let squareOfEvens2 =

Seq.map Square (Seq.filterIsEven numbers)

Если вы применяете LINQ, то подобное использование функций более высокого порядка должно показаться вам очень знакомым. А все дело в том, что корни LINQ уходят глубоко в функциональное программирование. По сути, вы можете легко адаптировать задачу возведения в квадрат четных чисел под C# с применением методов LINQ:

varsquareOfEvens =

numbers

.Where(IsEven)

.Select(Square);

Это транслируется в следующий синтаксис LINQ-запроса:

varsquareOfEvens = from number in numbers

whereIsEven(number)

select Square(number);

Использование LINQ в коде на C# или Visual Basic позволяет эксплуатировать некоторые возможности функционального программирования в повседневной работе. И это отличный способ освоения методик такого программирования.

Когда вы начнете регулярно использовать функции более высокого порядка, вы в конце концов придете к такой ситуации, в которой захотите создать небольшую, очень специфическую функцию для передачи в функцию более высокого порядка. Для решения этой задачи «функциональные» программисты используют лямбда-функции. Это просто функции, которые вы определяете, не присваивая имен. Обычно они очень маленькие и имеют сугубо специфическое применение. Например, вот еще один способ, которым вы могли бы возводить в квадрат четные числа, используя лямбду:

letwithLambdas =

numbers

|>Seq.filter (fun x -> x % 2 = 0)

|>Seq.map (fun x -> x * x)

Единственное различие между этим и предыдущим кодом заключается в том, что Square и IsEven определены как лямбды. В F# вы объявляете лямбда-функцию ключевым словом fun. Лямбды следует использовать только для объявления функций одного специфического применения, потому что их сложно задействовать вне области видимости, в которой они были определены. По этой причине Square и IsEven — плохой выбор на роль лямбда-функций, так как они полезны во многих ситуациях.

Карринг и частичное применение

Теперь вы знаете почти все основы, необходимые для того, чтобы приступить к работе с F#, но есть еще одна концепция, которую вы должны освоить. В предыдущих примерах оператор |> и стрелки в сигнатурах типов из F# Interactive тесно связаны с концепцией так называемогокарринга.

Карринг (currying) — это разбиение функции со множеством аргументов на серию функций, каждая из которых принимает один аргумент, и в конечном счете они дают тот же результат, что и исходная функция. Карринг, по-видимому, является в этой статье самой трудной концепцией для .NET-разработчика, особенно из-за того, что его часто путают с частичным применением (partialapplication). Работу обеих концепций иллюстрирует следующий пример:

letmultiply x y =

x * y

let double = multiply 2

letten = double 5

Прямо сейчас вы должны увидеть поведение, отличающееся от того, которое вы наблюдали бы в большинстве императивных языков. Второе выражение создает новую функцию double передачей одного аргумента в функцию, которая принимает два. Результат — функция, которая принимает один аргумент типа int и возвращает то же самое, как если бы вы вызвали multiply с x, равным 2, и y, равным этому аргументу. По своему поведению этот код эквивалентен:

let double2 z = multiply 2 z

Зачастую в таком случае ошибочно полагают, что multiply разбивается до double. Но это верно лишь отчасти. Функция multiply подвергается каррингу, однако это происходит, когда она определена, так как в F# функции подвергаются каррингу по умолчанию. Когда создается функция double, точнее сказать, что функция multiply применяется частично.

Давайте пройдем все этапы в деталях. Еще раз повторю, что при карринге функция с множеством аргументов разбивается на серию функций с одним аргументом, которые в конечном счете дают тот же результат, что и исходная. Функция multiply имеет следующую сигнатуру типа согласно F# Interactive:

valmultiply :int ->int ->int

К этому моменту мы расшифровали, что multiply является функцией с двумя аргументами типа int и возвращаемым значением того же типа. Теперь я поясню, что происходит на самом деле. Функция multiply в действительности состоит из двух функций. Первая принимает один аргумент типа int и возвращает другую функцию, в конечном счете связывающую x с конкретным значением. Эта функция также принимает один аргумент типа int, которое можно считать значением, связываемым с y. После вызова этой второй функции x и y связаны со своими значениями, поэтому результатом является произведение x на y, как определено в теле функции double.

Чтобы создать double, первая функция в цепочке функций multiply оценивается как частично применяемая multiply. Полученной функции присваивается имя double. Когда оценивается double, она использует свой аргумент вместе с частично примененным значением для создания результата.

Использование F# и функционального программирования

Теперь, когда у нас есть достаточный словарь для того, чтобы начать работу с F# и окунуться в функциональное программирование, перед вами открывается уйма вариантов, что делать дальше.

Окно F# Interactive позволяет исследовать код на F# и быстро создавать сценарии (scripts) F#. Оно также полезно для рутинной проверки поведения библиотечных функций .NET без обращения к справочным файлам или поиску в Интернете.

F# превосходен в выражении сложных алгоритмов, поэтому вы можете инкапсулировать соответствующие части кода своего приложения в F#-библиотеки, чтобы потом вызывать их из других .NET-языков. Это особенно полезно в инженерных или параллельных приложениях.

Наконец, вы можете использовать методики функционального программирования в своей повседневной разработке для .NET даже без написания кода на F#. Просто используйте LINQ вместо циклов for или foreach. Попробуйте применять делегаты для создания функций более высокого порядка. Ограничьте себя в использовании изменяемости и побочных эффектов в своих императивных языках. Как только вы начнете писать код в функциональном стиле, вы очень скоро захотите создавать больше кода на F#.

Тема 3. Функциональное программирование на языке Haskell

Haskell - строго типизированный язык. Это означает, что любая конструкция в языке, задающая некоторый объект, имеет определенный тип, который можно «вычислить» еще до начала выполнения программы, то есть статически. Таким же свойством обладают большинство современных языков программирования, такие как Паскаль, Java, Си++ и многие другие. Труднее привести пример не строго типизированного языка (если, конечно, не считать некоторых отступлений от строгой типизации в упомянутых выше языках, сделанных для удобства практического программирования, таких, например, как тип Pointer в языке Паскаль). Пожалуй, самым известным из языков, изначально не имеющих строгой типизации, является первый язык функционального программирования Лисп.

Основу системы типов языка Haskell составляют элементарные встроенные типы данных: целые, представленные двумя подтипами с идентификаторами Integer и Int, вещественные, также с двумя подтипами Float и Double, логические, имеющие идентификатор типа Bool и символьные (Char). Заметим сразу же, что все идентификаторы в

Haskell чувствительны к регистру букв, так что integer, Integer и INTEGER – это три разных идентификатора. Регистр первой буквы идентификатора определяет также, к какому из двух «миров» относится идентификатор: если идентификатор начинается с заглавной буквы, то он обозначает встроенный или определенный программистом тип или класс. Идентификаторы объектов – значений простых и сложных типов, в том числе функций – начинаются со строчной буквы или символа подчеркивания. Идентификаторы, как и в других языках программирования, строятся из букв, подчеркиваний и цифр, однако в Haskell допустимо использовать для построения идентификаторов также символ "'" («апостроф»). Ни апостроф, ни цифра не могут быть первым символом идентификатора. Заметим, что апостроф традиционно используется для построения имен функций, вспомогательных по отношению к функции, заданной тем же именем, только без апострофов. Например, если мы определяем функцию с именем factorial и в качестве вспомогательных для нее хотим определить еще две функции, не имеющие самостоятельного значения, то имена этих функций по традиции, скорее всего, будут factorial' и factorial''.

Четыре базовых типа - это, конечно, типы, определяющие наборы хорошо известных значений целого, вещественного, логического и символьного типов. Отметим несколько особенностей базовых типов Haskell, непривычных по другим языкам программирования.

Тип Integer определяет потенциально бесконечный набор целых чисел произвольной длины. В операциях над целыми типа Integer никогда не происходит «переполнения» (конечно, в пределах выделенной для работы программы памяти). Для повышения эффективности работы программ можно использовать и вполне традиционные целые ограниченной длины. Для таких «ограниченных» целых используется идентификатор типа Int. Последовательность цифр, возможно, предваренная знаком '–', представляет в программе целое число (как говорят, целые числа имеют литеральные обозначения в виде последовательности цифр).

Вещественные числа типов Float и Double определяются вполне традиционно и имеют также традиционные литеральные обозначения, такие как 3.14, -2.71828 или 0.12е-10.

Символьный тип также имеет литеральные обозначения для своих значений, и они тоже вполне традиционны. Так, обозначение 'а' представляет символ а.

Логический тип представлен двумя значениями – истина и ложь. Литеральных обозначений для логических значений в языке нет, однако, имеются два стандартных идентификатора – True и False, обозначающие истинное и ложное значения соответственно.

В программе можно вводить свои собственные идентификаторы для имеющихся значений. Такая возможность совершенно эквивалентна средствам описания констант в различных языках программирования. Например, идентификатор school можно ввести для обозначения константы 239 с помощью следующего фрагмента программы:

school = 239

Если мы хотим явно указать тип для нового идентификатора объекта, то это можно сделать с помощью конструкции определения типа. Например, если мы хотим указать, что введенный идентификатор school должен представлять значение типа Integer, то перед определением значения следует написать school :: Integer

Такое уточнение типа не обязательно, потому что система программирования на языке Haskell обязана сама устанавливать (выводить) типы всех встречающихся объектов и выражений, но иногда это может все же оказаться существенным. Так, например, литерал 239 в предыдущем примере может обозначать как целое типа Int, так и целое типа Integer в зависимости от контекста. Явное указание типа Integer устраняет неоднозначность.

Значения произвольных типов можно объединять в кортежи. Аналогом этого понятия в языке Паскаль будет определение типа записи. Объединяемые в кортеж значения просто перечисляются в скобках через запятую. Например, обозначение (2, 'a') представляет кортеж из двух значений - целого числа 2 и символа 'а'. Заметим, что типом этого кортежа будет (Int, Char), так что можно написать следующий фрагмент программы, в котором вводится новое обозначение для этого кортежа и явно указывается его тип:

pair :: (Int, Char) pair = (2, 'a')

Разумеется, кортежи сами могут входить в состав других кортежей. Например, следующий фрагмент программы определяет идентификатор для кортежа, в состав которого входит другой кортеж.

myValue :: (Int, (Char, Char), Bool) myValue = (366, ('A', 'K'), True)

Над значениями можно выполнять определенные в языке операции и применять стандартные функции. Полный набор стандартных функций можно посмотреть, например, в официальном пересмотренном сообщении о языке Haskell'98, или в других подробных документах по языку. Мы будем постепенно вводить новые операции и стандартные функции по мере необходимости, а сейчас пока отметим, что в языке имеется достаточно обычный набор арифметических и логических операций, а также операций сравнения и функций преобразования значений из одних

типов в другие. Запись выражений также достаточно традиционна, так что не вызывает никакого удивления, что, скажем, выражение 2+3 записано правильно и при вычислении выдает значение 5, а выражение 3<(2+2) выдает значение истина. Наиболее необычными являются две особенности записи выражений.

Во-первых, при вызове функций аргументы отделяются от идентификатора функции не привычными скобками, а пробелом. Если аргументов несколько, то сами аргументы тоже отделяются друг от друга пробелами. Так, например, функцию вычисления синуса, определенную для вещественных аргументов, можно вызвать с помощью конструкции sin 0.5

а функцию определения максимального из двух любых упорядоченных значений можно вызвать (в предположении, что идентификатор x обозначает некоторое целое значение), скажем, так: max 3 (x+1)

Вторая существенная особенность состоит в том, что операторы, задающие арифметические и другие операции, вообще говоря, синтаксически неотличимы от обычных двуместных функций. Я имею в виду, что вызов операции, подобной сложению двух целых, можно записывать не только в виде бинарной операции, расположенной между аргументами, но и так, как это принято для обычных двуместных функций. Для превращения знака бинарной операции в двуместную функцию надо лишь заключить знак операции в скобки, так что запись

(+) x y

полностью эквивалентна записи

x + y

Обратное тоже верно. Для того, чтобы превратить обычный идентификатор функции двух аргументов в бинарный оператор достаточно заключить идентификатор функции в обратные апострофы, так что приведенное выше обращение к функции вычисления максимального из двух упорядоченных значений можно было бы записать в виде применения бинарной операции:

3 `max` (x+1)

Конечно, для того, чтобы написать хоть сколько-то полезную программу, необходимо помимо новых идентификаторов для объектов и написания выражений уметь самому определять новые функции. Каждая функция в Haskell – это тоже некоторое значение, для которого определен тип. В типе функции указывают типы ее аргументов и тип значения функции, при этом типы аргументов и значения функции отделяются друг от друга символом '->', так что, например, тип функции одного вещественного аргумента с вещественным результатом (такой, как, например, функция вычисления синуса) можно записать в виде

Double -> Double

а тип функции с двумя целыми аргументами и одним логическим результатом (такой, как, например, операция сравнения двух целых значений по величине) можно записать в виде

Int -> Int -> Bool

Саму функцию можно определить с помощью «уравнения», в котором определяется, как функция должна себя вести, если ей задать значение аргумента. Давайте, например, определим функцию удвоения, которая удваивает значение своего вещественного аргумента и выдает получившееся значение. Для этого зададим идентификатор функции twice, зададим ее тип и напишем уравнение, в котором покажем, что вызов этой функции с заданным значением аргумента эквивалентен выражению, в котором это значение умножается на два:

twice :: Double -> Double twice x = 2 * x

В уравнении, определяющем поведение функции twice, можно выделить левую часть, задающую форму вызова функции, и правую часть, в которой записывается выражение, заменяющее вызов функции в тот момент, когда будет задано значение ее аргумента. Если функция twice определена, то вычисление выражения twice 5.5 можно представить себе следующим образом. Сначала происходит сопоставление фактического значения аргумента 5.5 с формальным аргументом функции, заданном в уравнении, определяющем поведение функции. Потом вызов функции заменяется правой частью уравнения, в которой вместо формального аргумента используется сопоставленное с ним значение фактического аргумента. Таким образом, после сопоставления и замены вместо выражения twice 5.5 получаем выражение 2 * 5.5, которое после вычисления (применения операции умножения) дает значение 11. Процесс преобразования (вычисления) выражения можно записать следующим образом:

twice 5.5 ⇒ 2 * 5.5 ⇒ 11

Преобразование выражений, подобное только что приведенному, называют еще редукциями. Таким образом, можно сказать, что вычисление выражений в Haskell (исполнение программы) осуществляется с помощью последовательных редукций исходного выражения.

Определение функции может быть рекурсивным, то есть в правой части уравнения может быть вызов определяемой функции. В этом случае в процессе преобразования выражения, содержащего вызов рекурсивной функции, может получаться выражение, также содержащее вызов той же самой функции. Для того, чтобы процесс вычисления мог закончиться, необходимо использовать условные выражения, которые приводят к

выбору одной из двух альтернатив при вычислении сложных выражений. Условное выражение имеет вид

if <условие> then <выражение-"то"> else <выражение-"иначе">

При вычислении условного выражения прежде всего вычисляется условие. Тип вычисленного выражения-условия должен быть логическим (Bool). Если вычисленное значение оказывается истинным, то вместо всего условного выражения подставляется выражение-"то", а выражение"иначе" отбрасывается. Если же наоборот, условие оказалось ложным, то отбрасывается выражение-"то", а вместо всего условного выражения остается только часть, определенная выражением-"иначе".

Зададим определение простой рекурсивной функции, предназначенной для вычисления факториала заданного целого числа. Простое и естественное определение этой функции может выглядеть следующим образом:

factorial :: Integer -> Integer

factorial n = if n == 0 then 1 else n * factorial (n-1)

Проследим за тем, как происходит вычисление выражения

factorial 3, записывая последовательно все этапы преобразования

выражения в соответствии с определением функции factorial (листинг

1.6).

Листинг 1.6. Процесс преобразования выражения при вычислении факториала числа

factorial 3 ⇒

if 3 == 0 then 1 else 3 * factorial 2 ⇒

if False then 1 else 3 * factorial 2 ⇒

3 * factorial 2 ⇒

3 * if 2 == 0 then 1 else 2 * factorial 1 ⇒

3 * 2 * factorial 1 ⇒

3 * 2 * if 1 == 0 then 1 else 1 * factorial 0 ⇒

3 * 2 * 1 * factorial 0 ⇒

3 * 2 * 1 * if 0 == 0 then 1 else 0 * factorial (-1) ⇒

3 * 2 * 1 * 1 ⇒

Вместо использования условного выражения можно записать несколько уравнений, определяющих поведение функции при различных значениях аргумента. Так, например, можно переопределить функцию вычисления факториала, задав для нее два уравнения, обусловленных выражениями-«сторожами», определяющими, какое из двух уравнений на самом деле следует применять.

factorial :: Integer -> Integer

factorial n | n == 0 = 1

factorial n | n > 0 = n * factorial (n-1)

или короче

factorial :: Integer -> Integer factorial n | n == 0 = 1

| n > 0 = n * factorial (n-1)

Обратите внимание, что в новом варианте функции сторожа не покрывают всех возможных значений аргумента. Если написать бессмысленный вызов функции factorial -3, то при нашем первоначальном определении вычисление выражения в программе уйдет в бесконечный цикл; преобразование выражения никогда не сможет нормально закончиться. Во втором случае система программирования сразу же выдаст сообщение об ошибке, поскольку ей не удастся найти уравнение со сторожем, который при вычислении выдаст истинное значение.

Еще один способ определения той же функции состоит в том, что в уравнениях, определяющих функцию, можно сразу же задать случай, когда аргументом вызова будет нулевое значение. Определение функции теперь может выглядеть так:

factorial :: Integer -> Integer

factorial 0 = 1

factorial n = n * factorial (n-1)

В этом определении тоже происходит выбор нужного уравнения из двух возможных вариантов. Порядок задания уравнения здесь важен. Сначала рассматривается первое уравнение, в котором фактический аргумент сопоставляется с нулевой константой. Сопоставление возможно только в том случае, когда сам этот аргумент равен нулю. Если же аргумент больше нуля, то будет выбрано второе уравнение, в котором сопоставление всегда произойдет успешно, поскольку с идентификатором n может сопоставиться любое значение. После замены выражения вызова на правую часть будет произведено новое сопоставление и выбор уравнения и т.д. Вычисление факториала будет, конечно, происходить по тому же самому алгоритму. Заметим, что в этом последнем способе задания функции опять возможным становится задание отрицательного значения аргумента, при этом программа будет выполняться бесконечно, а никакого сообщения об ошибке выдано не будет.

Напишем еще несколько функций, выполняющих те или иные арифметические действия, просто для того, чтобы освоиться с манерой написания функций в языке Haskell. Определим функцию, которая по заданным натуральным числам определяет их наибольший общий делитель согласно алгоритму Евклида. Назовем эту функцию gcd (greatest common divider). Идея Евклида состоит в том, что если ни одно из чисел не равно нулю, то наибольший общий делитель таких двух чисел равен наибольшему общему делителю наименьшего из них и остатка от деления большего на меньшее. Поскольку остаток от деления одного числа на

другое можно вычислить с помощью стандартной бинарной операции mod, то функцию gcd можно определить следующим образом (листинг 1.7):

Листинг 1.7. Наибольший общий делитель двух чисел

gcd :: Integer -> Integer -> Integer -- в первом уравнении обеспечиваем, -- чтобы первый аргумент был больше второго. -- функция определена только для неотрицательных аргументов gcd m n | m < 0 = error "gcd: Negative argument" | n < 0 = error "gcd: Negative argument" -- собственно алгоритм Евклида: gcd m 0 = m gcd m n = gcd n (m `mod` n)

В этом примере использованы различные виды уравнений, определяющих одну и ту же функцию. Стандартная функция error выводит в стандартный выходной поток сообщение, являющееся ее аргументом и возвращает в качестве результата «неопределенное значение». Если такое неопределенное значение действительно будет получено в результате работы программы, то программа будет завершена аварийно. Как и в только что показанном примере функция error обычно используется для вывода диагностических сообщений и аварийного завершения работы программы в случае неверно заданных аргументов функции.

Тема 4. "Искусственный интеллект".

1. Понятие Основные термины и определения.

2. Предпосылки и история развития ИИС.

3. Правила формулировки условий задач и выбор модели решения.

1. Понятие "искусственный интеллект". Основные термины и определения.

Понятие "искусственный интеллект" многогранно, и разные авторы дают разные определения.

Искусственный интеллект – это метафорическое понятие для обозначения системы созданных людьми средств, воспроизводящих определенные функции человеческого мышления. (Философский словарь)

Искусственный интеллект – это искусственная система, имитирующая решение человеком сложных задач. (Энциклопедический словарь по информатике)

Определение, которого мы будем придерживаться в нашем курсе: Искусственный интеллект – это программная система, имитирующая на компьютере мышление человека.

Программы, реализующие элементы искусственный интеллекта, называют интеллектуальными информационными системами (ИИС).

Система считается интеллектуальной, если в ней реализованы следующие три базовые функции.

1. Функция представления и обработки знаний. Интеллектуальная система должна быть способна накапливать знания об окружающем мире, классифицировать и оценивать их с точки зрения прагматики и непротиворечивости, инициировать процессы получения новых знаний, соотносить новые знания со знаниями, хранящимися в базе знаний.

2. Функция рассуждения. Интеллектуальная система должна быть способна формировать новые знания с помощью логического вывода и механизмов выявления закономерностей в накопленных знаниях, получать обобщенные знания на основе частных знаний и логически планировать свою деятельность.

3. Функция общения. Интеллектуальная система должна быть способна общаться с человеком на языке, близком к естественному языку (ЕЯ) и получать информацию через каналы, аналогичные тем, которые использует человек при восприятии окружающего мира (прежде всего, зрительный и звуковой). Также система должна уметь формировать «для себя» или по просьбе человека объяснения собственной деятельности (т. е. отвечать на вопросы типа «Как я это сделал?»), оказывать человеку помощь за счет знаний, которые хранятся в ее памяти, и логических средств рассуждения.

Основная цель ИИС – это реализовать информационный процесс максимально приближено к мыслительному процессу человека. Целями интеллектуальных информационных технологий являются, во-первых, расширение круга задач, решаемых с помощью компьютеров, особенно в слабоструктурированных предметных областях, и, во-вторых, повышение уровня интеллектуальной информационной поддержки современного специалиста.

Так как интеллект присущ только человеку, а интеллект – это есть совокупность знаний и навыков их обработки, то для создания ИИС мыслительные процессы формализуются, раскладываются на простейшие операции и их связки, а затем программируются исходя из особенностей задачи и выбранного языка программирования.

2. Предпосылки и история развития ИИС.

Искусственный интеллект (ИИ) как научное направление, связанное с попытками формализовать мышление человека, имеет длительную историю. Еще Платон, Аристотель, Р. Декарт, Г.В. Лейбниц, Дж. Буль и многие другие исследователи на уровне современных им знаний стремились описать мышление как совокупность некоторых элементарных операций, правил и процедур. Перечислим самые значимые вехи в эволюции научной мысли, оказавшие влияние на развитие идей интеллектуальных информационных систем. В начале XVII века Рене Декарт предположил, что животное – некий сложный механизм, тем самым сформулировав механистическую теорию. В 1910-1913 гг. Бертран Рассел и А. Н. Уайтхед опубликовали работу «Принципы математики», которая произвела революцию в формальной логике. В 1941 Конрад Цузе построил первый работающий программно-контролируемый компьютер. Качественно новый период развития искусственного интеллекта связан с появлением в научных лабораториях ЭВМ и с публикацией книги Н. Винера "Кибернетика или управление и связь в животном и машине" появившейся еще ранее книги У. Росс Эшби "Введение в кибернетику".УорренМаккалок